package sword_offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @Class sword_offer.Code35
 * @Description 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 * <p>
 * 例如:
 * 给定二叉树:[3,9,20,null,null,15,7],
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回其层次遍历结果：
 * <p>
 * [
 * [3],
 * [20,9],
 * [15,7]
 * ]
 * <p>
 * <p>
 * 提示：
 * 节点总数 <= 1000
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-19 19:45
 */
public class Code35 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(3);
        head.left = new TreeNode(9);
        head.right = new TreeNode(20);
        head.right.left = new TreeNode(15);
        head.right.right = new TreeNode(7);
        List<List<Integer>> res = levelOrder(head);
        for (List<Integer> re : res) {
            System.out.println(re);
        }
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        TempQueue<TreeNode> tempQueue = new TempQueue<>();
        tempQueue.push(root);
        int level = 1;
        while (tempQueue.getLength() != 0) {
            LinkedList<Integer> tmp = new LinkedList<>();
            int len = tempQueue.getLength();
            for (int i = 0; i < len; i++) {
                TreeNode node = tempQueue.getTop();
                if ((level & 1) == 1) {
                    tmp.addLast(node.val);
                } else {
                    tmp.addFirst(node.val);
                }
                if (tempQueue.getTop().left != null) {
                    tempQueue.push(tempQueue.getTop().left);
                }
                if (tempQueue.getTop().right != null) {
                    tempQueue.push(tempQueue.getTop().right);
                }
                tempQueue.pop();
            }
            level++;
            res.add(tmp);
        }
        return res;
    }
}
/*
对奇数层和偶数层的结点保存使用LinkedList来存储
因为LinkedList有addFirst和addLast方法
 */